package leetcode.code0652;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import leetcode.helper.tree.TreeNode;

public class Solution {
	
	Set<String> keys;
	List<TreeNode> ans;
	Set<String> trees;

	public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
		ans = new ArrayList<>();
		keys = new HashSet<>();
		trees = new HashSet<>();
		this.f(root);
		return ans;
	}

	private String f(TreeNode root) {
		if (root == null) {
			return "300";
		}
		StringBuffer tree = new StringBuffer();
		tree.append(root.val).append('-').append(this.f(root.left)).append('-').append(this.f(root.right));
		if(!trees.add(tree.toString()) && keys.add(tree.toString())) {
			ans.add(root);
		}
		return tree.toString();
	}

}
